package org.algorithm.biubiu.wheel_1.链表;

import org.algorithm.biubiu.wheel_1.common.ListNode;

/**
 * @author jiazhaoxin
 * @Date 2022/2/26
 * @Desc
 */
public class 合并K个升序链表 {



    public ListNode mergeKLists(ListNode[] lists) {
        if(lists==null||lists.length==0){
            return null;
        }
        return merge(lists,0,lists.length-1);
    }



    public ListNode merge(ListNode[] lists,int left,int right){
        if(right==left) return lists[left];
        int mid = left + (right-left)/2;
        ListNode node1 = merge(lists,left,mid);
        ListNode node2 = merge(lists,mid+1,right);
        return  merge2(node1,node2);
    }

    public ListNode merge2(ListNode node1,ListNode node2){
        if(node1==null) return node2;
        if(node2==null) return node1;
        if(node1.val<node2.val){
            node1.next = merge2(node1.next,node2);
            return node1;
        }else{
            node2.next = merge2(node2.next,node1);
            return node2;
        }
    }
}
